package _11_整理题目._2_二叉树_递归_dfs_bfs._遍历;


import org.junit.Test;
import util.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
 * 例如：
 * 给定的二叉树是{3,9,20,#,#,15,7},
 * 该二叉树之字形层序遍历的结果是
 * [
 * [3],
 * [20,9],
 * [15,7]
 * ]
 * 
 * bfs
 * 相比较 层次遍历 来说，只是增加了一个 level++ 根据 level % 2 == 1 来判断层级
 * 注意 level 变量要加在 while() 之外
 * 奇数层使用 Collections.reverse() 翻转一下 再 add
 * 为了避免翻转操作，可以使用 双端队列 分别从两侧插入值
 * 
 * dfs：二叉树的 dfs 并不是 斜向之字形
 * 写法和 bfs 一样，只是使用 stack，每次先装 右节点，再装 左节点
 * 
 */
public class _013_二叉树的之字形层序遍历 {
    
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        if (root == null) return new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
    
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        int level = 0;
        while (!queue.isEmpty()) {
            int n = queue.size();
            ArrayList<Integer> temp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            if (level++ % 2 == 1) Collections.reverse(temp);
            result.add(temp);
        }
        return result;
    }
    
    @Test
    public void main() {
        Integer[] input = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
        TreeNode root = TreeNode.getTreeFromArray(input);
        ArrayList<ArrayList<Integer>> result = zigzagLevelOrder(root);
        result.forEach(list -> System.out.println(list));
    }
    
    
    public ArrayList<Integer> dfs(TreeNode root) {
        if (root == null) return new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        
        ArrayList<Integer> result = new ArrayList<>();
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right!=null) stack.push(node.right);
            if (node.left!=null)  stack.push(node.left);
        }
        return result;
    }
    
    @Test
    public void testDfs() {
        Integer[] input = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
        TreeNode root = TreeNode.getTreeFromArray(input);
        ArrayList<Integer> dfsResult = dfs(root);
        System.out.println(dfsResult);
    }
}
